# Darren
# 2025年02月23日22时35分17秒
# 1、完成二叉树中序，后序，层序遍历
import random


class Node:
    def __init__(self, elem):
        self.elem = elem
        self.lchild = None
        self.rchild = None


class Tree:
    def __init__(self):
        self.root = None
        self.arr = []

    def insert_node(self, item):  # 层序建树
        node: Node = Node(item)
        queue = self.arr
        queue.append(node)
        if not self.root:
            self.root = node
        elif not queue[0].lchild:
            queue[0].lchild = node
        else:
            queue[0].rchild = node
            queue.pop(0)

    def in_order(self, item: Node):  # 中序遍历
        if item:
            self.in_order(item.lchild)
            print(item.elem, end=" ")
            self.in_order(item.rchild)

    def post_order(self, item: Node):  # 后序遍历
        if item:
            self.post_order(item.lchild)
            self.post_order(item.rchild)
            print(item.elem, end=" ")

    def level_order(self):  # 层序遍历
        print("层序遍历：", end="")
        queue = [self.root]
        while queue:
            node: Node = queue.pop(0)
            print(node.elem, end=" ")
            if node.lchild:
                queue.append(node.lchild)
            if node.rchild:
                queue.append(node.rchild)


tree = Tree()
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for x in arr:
    tree.insert_node(x)
print("中序遍历：", end="")
tree.in_order(tree.root)
print()
print("后序遍历：", end="")
tree.post_order(tree.root)
print()
tree.level_order()
print()
print('-' * 50)


# 2、完成快速排序，堆排序
class Sort:
    def __init__(self, n, nums_range):
        self.n = n
        self.nums_range = nums_range
        self.arr = []
        for i in range(n):
            self.arr.append(random.randint(1, nums_range - 1))

    def partition(self, left, right):  # 划分
        arr = self.arr
        pivot = arr[left]
        while left < right:
            while arr[right] >= pivot and left < right:
                right -= 1
            arr[left] = arr[right]
            while arr[left] <= pivot and left < right:
                left += 1
            arr[right] = arr[left]
        arr[left] = pivot
        return left

    def quick_sort(self, low, high):  # 快排
        if low < high:
            k = self.partition(low, high)
            self.quick_sort(low, k - 1)
            self.quick_sort(k + 1, high)

    def adjust_min_heap(self, parent_pos, arr_len):  # 调整为小顶堆
        arr = self.arr
        dad = parent_pos
        son = 2 * dad + 1  # 当前父节点的左孩子
        while son < arr_len:  # 结点有左孩子，进入循环
            if son + 1 < arr_len and arr[son + 1] < arr[son]:  # 防止数组越界
                son += 1  # 使 son为 dad孩子的最小节点
            if arr[dad] > arr[son]:
                arr[son], arr[dad] = arr[dad], arr[son]  # 父节点较大，则交换
            if 2 * son + 1 < arr_len:  # 向下循环调整子树
                dad = son
                son = 2 * dad + 1
            else:
                break

    def heap_sort(self):  # 堆排（逆序）
        arr = self.arr
        for x in range(self.n // 2 - 1, -1, -1):
            self.adjust_min_heap(x, self.n)
        for y in range(self.n - 1, -1, -1):
            arr[0], arr[y] = arr[y], arr[0]
            self.adjust_min_heap(0, y)


nums = Sort(10, 100)
print(f"序列：{nums.arr}")
nums.quick_sort(0, nums.n - 1)
print(f"快排：{nums.arr}")
nums.heap_sort()
print(f"堆排：{nums.arr}")
